package com.ljy.my_study.lintcode.前序遍历和中序遍历树构造二叉树;

/**
 * @author James
 * @date 2018年9月28日
 */
public class TestMain {
	// 描述
	// 根据前序遍历和中序遍历树构造二叉树.
	//
	// 你可以假设树中不存在相同数值的节点
	//
	// 您在真实的面试中是否遇到过这个题？
	// 样例
	// 给出中序遍历：[1,2,3]和前序遍历：[2,1,3]. 返回如下的树:
	//
	// 2
	// / \
	// 1 3
	public static void main(String[] args) {
		int[] nums= {8};
		System.out.println(buildTree(nums,nums));
	}

	public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length==0){
            return null;
        }
        return buildCore(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    private static TreeNode buildCore(int[] preorder,int preSt,int preEnd,int[] inorder,int inSt,int inEnd){
        //前序遍历第一个节点是根节点
        int rootValue = preorder[preSt];
        TreeNode root = new TreeNode(rootValue);

        //前序序列只有根节点
        if(preSt == preEnd){
            return root;
        }
        //遍历中序序列，找到根节点的位置
        int rootInorder = inSt;
        while(inorder[rootInorder]!=rootValue&&rootInorder<=inEnd){
            rootInorder++;
        }

        //左子树的长度
        int leftLength = rootInorder - inSt;
        //前序序列中左子树的最后一个节点
        int leftPreEnd = preSt + leftLength;

        //左子树非空
        if(leftLength>0){
            //重建左子树
            root.left = buildCore(preorder,preSt+1,leftPreEnd,inorder,inSt,inEnd);
        }
        //右子树非空
        if(leftLength < preEnd - preSt){
            //重建右子树
            root.right = buildCore(preorder,leftPreEnd +1,preEnd,inorder,rootInorder+1,inEnd);
        }
        return root;
    }

	public static class TreeNode {
		public int val;
		public TreeNode left, right;

		public TreeNode(int val) {
			this.val = val;
			this.left = this.right = null;
		}

		@Override
		public String toString() {
			return "{\"val\":\"" + val + "\",\"left\":\"" + left + "\",\"right\":\"" + right + "\"} ";
		}
		
	}
}
